import java.util.*;


class MinStack {
    private Stack<Integer> stack;
    private Stack<Integer> minStack;//存储阶段性最小值
    private int minValue;

    public MinStack() {
        stack=new Stack<>();
        minStack=new Stack<>();
    }

    public void push(int val) {
        stack.push(val);
        if (minStack.empty()){
            minStack.push(val);
        }else {
            if (val<=minStack.peek()){
                minStack.push(val);
            }
        }
    }

    public void pop() {
        if (!stack.empty()){
            int ret=stack.pop();
            if (minStack.peek()==ret){
                minStack.pop();
            }
        }
    }

    public int top() {
        //获取stack栈顶元素
        if (stack.empty()){
            return -1;
        }
        return stack.peek();
    }

    public int getMin() {
        //获取minStack栈顶元素
        if (minStack.empty()){
            return -1;
        }
        return minStack.peek();
    }
}

public class Main {

    public static void insertSort(int[] arr){
        for (int i = 1; i < arr.length; i++) {
            int tmp=arr[i];
            int j = i-1;
            for (; j >=0; j--) {
                if (arr[j]>tmp){
                    arr[j+1]=arr[j];
                }else {
                    break;
                }
            }
            arr[j+1]=tmp;
        }
    }

    public static void shellSort(int[] arr){
        int gap=arr.length/2;
        while (gap>1){
            shell(arr,gap);
            gap/=2;
        }
    }

    private static void shell(int[] arr, int gap) {
        for (int i = gap; i < arr.length; i++) {
            int tmp=arr[i];
            int j=i-gap;
            for (;j>=0;j--){
                if (arr[j]>tmp){
                    arr[j+1]=arr[j];
                }else {
                    break;
                }
            }
            arr[j+1]=tmp;
        }
    }

    public static void selectSort(int[] arr){
        for (int i = 0; i < arr.length; i++) {
            //1、找到待排序序列中的最小值
            int minIndex=i;
            for (int j = i+1; j < arr.length; j++) {
                if (arr[j]<arr[minIndex]){
                    minIndex=j;
                }
            }
            //2、将待排序序列中的最小值放到待排序序列起始位置
            swap(arr,minIndex,i);
        }
    }

    public static void selectSort2(int[] arr){
       int left=0;
       int right=arr.length-1;
       while (left<right){
           int minIndex=left;
           int maxIndex=left;
           for (int i = left+1; i <=right; i++) {
               if (arr[i]<arr[minIndex]){
                   minIndex=i;
               }
               if (arr[i]>arr[maxIndex]){
                   maxIndex=i;
               }
           }
          swap(arr,left,minIndex);
           if (maxIndex==left){
               maxIndex=minIndex;
           }
           swap(arr,right,maxIndex);

           left++;
           right--;
       }
    }

    private static void swap(int[] arr,int minIndex,int i){
        int tmp=arr[minIndex];
        arr[minIndex]=arr[i];
        arr[i]=tmp;
    }

    public static void heapSort(int[] array){
        //1、建立大根堆
        createBigHeap(array);
        //2、在大根堆上进行堆排序
        int end= array.length-1;
        while (end>0){
            swap(array,0,end);
            shiftDown(array,0,end);
            end--;
        }
    }

    private static void createBigHeap(int[] array) {
        for (int parent = (array.length-1)/2; parent >= 0; parent--) {
            shiftDown(array,parent,array.length);
        }
    }

    private static void shiftDown(int[] array, int parent, int length) {
        int child=2*parent+1;
        while (child<array.length){
            if (child+1<array.length && array[child+1]>array[child]){
                child++;
            }
            if (array[child]>array[parent]){
                swap(array,child,parent);
                parent=child;
                child=2*parent+1;
            }else {
                break;
            }
        }
    }

    public static void bubbleSort(int[] arr){
        for (int i = 0; i < arr.length-1; i++) {//i控制排序轮数 n个元素进行n-1轮就能完成排序，每进行一轮就会把当前未排序部分的最大元素移动到length-1-i位置
            boolean flag=false;
            for (int j = 0; j < arr.length-1-i; j++) {//j控制每一轮中相邻元素的比较操作
                if (arr[j+1]<arr[j]){
                    swap(arr,arr[j+1],arr[j]);
                    flag=true;
                }
            }
            //每一趟走完都判断flag的值，若仍为false，则说明数组已经处于有序状态。则直接返回，不再进行后续多余的轮次比较
            if (flag==false){
                return;
            }
        }
    }

    //快速排序 Hoare版
    public static void quickSort(int[] arr){
        quick(arr,0,arr.length-1);
    }

    private static void quick(int[] arr, int start, int end) {
        if (start>=end) return;
        //1、选择基准值进行划分
        int pivot=partion3(arr,start,end);
        //2、递归排序，分别对基准值左边的子数组和右子数组重复以上步骤（直到子数组元素个数为1（left==right）或者为0（left>right），此时整个数组就完成了排序）
        quick(arr,start,pivot-1);
        quick(arr,pivot+1,end);

    }

    private static int partionHoare(int[] arr, int start, int end) {
        int left=start;
        int right=end;
        int pivot=arr[start];

        while (left<right){
            while (right>left && arr[right]>pivot) right--;
            while (left<right && arr[left]<pivot) left++;
            swap(arr,left,right);
        }
        swap(arr,start,left);
        return left;
    }

    private static int partionHug(int[] arr, int start, int end) {
        int left=start;
        int right=end;
        int pivot=arr[start];

        while (left<right){
            while (right>left && arr[right]>pivot) right--;
            arr[left]=arr[right];

            while (left<right && arr[left]<pivot) left++;
            arr[right]=arr[left];
        }
        arr[left]=pivot;
        return left;
    }

    private static int partion3(int[] arr, int start, int end) {
        int prev=start;
        int cur= start+1;
        //int pivot=arr[start];

        while (cur <= end){
            //cur找到小于基准值的值，就把prev向后移动一位。如果此时cur与prev指针之间有间隔，则交换prev与cur所指向的元素，之后cur继续向后移动
            //若cur所指向的元素大于等于基准值，则cur直接向后移动
            if (arr[cur]<arr[start] && arr[++prev]!=arr[cur])
                swap(arr,cur,prev);
            cur++;
        }
        //持续这个过程，直到cur遍历完整个序列
        //当cur遍历完整个序列，就把基准值元素与prev所指向的元素进行交换，此时这个prev所指向的位置就是基准元素的最终正确位置
        swap(arr,prev, start);
        return prev;
    }

    public void moveZeroes(int[] nums) {
        int dest=-1,cur=0;
        while (cur<nums.length){
            if(nums[cur]!=0){
                dest++;
                int tmp=nums[dest];
                nums[dest]=nums[cur];
                nums[cur]=nums[dest];
            }
        }
    }

    public void duplicateZeros(int[] arr) {
        int cur=0,dest=-1,n=arr.length;
        //1、先找到最后一个需要复写的数
        while(cur<n){
            if(arr[cur]==0) dest+=2;
            else dest+=1;
            if(dest>=n-1) break;
            cur++;
        }
        //2、处理边界问题，dest可能越界
        if(dest==n){
            arr[n-1]=0;
            cur--;
            dest-=2;
        }
        //3、从后向前完成复写操作
        while(cur>=0){
            if(arr[cur]!=0) {
                arr[dest--]=arr[cur--];
            }else{
                arr[dest--]=0;
                arr[dest--]=0;
                cur--;
            }
        }
    }


    public static void main(String[] args) {
        //创建数组：int[] arr = {1, 2, 3, 4, 5} 或者 int[] arr = new int[5]
        int[] arr={6,5,2,1,4,7,8};
        //insertSort(arr);
        quickSort(arr);
        for (int i = 0; i < arr.length; i++) {
            System.out.println(arr[i]);
            System.out.println();
        }
    }
}


class Main2 {
    /**
     * 左括号必须用相同类型的右括号闭合。
     * 左括号必须以正确的顺序闭合。
     * 每个右括号都有一个对应的相同类型的左括号。
     * ()，{}，[]
     * @param s
     * @return
     */
    public boolean isValid(String s) {
        Stack<Character> stack=new Stack<Character>();
        for (int i = 0; i < s.length(); i++) {
            char c=s.charAt(i);
            if (c=='(' || c=='[' || c=='{'){
                //c为左括号就添加进来等着对称匹配
                stack.push(c);
            }else {
                //c为右括号
                //此时栈中可能有左括号等着匹配，也可能为空（无法匹配）
                if (stack.empty()){
                    return false;
                }
                //不为空，则栈中存放的是左括号，那就判断c与栈顶元素是否匹配（因为两括号必须要对称匹配）
                char top=stack.peek();
                if (c==')' && top=='(' || c==']' && top=='[' || c=='}' && top=='{'){
                    //对称匹配了则弹出此左括号
                    stack.pop();
                }else {
                    //遇到一个右括号无法与栈顶左括号对称匹配，则无法匹配
                    return false;
                }
            }
        }
        //如果s遍历完发现栈中不为空，即栈中仍有残存左括号未进行匹配，不匹配
        if (!stack.empty()){
            return false;
        }
        //否则匹配
        return true;
    }

    public static int evalRPN(String[] tokens) {
        Stack<Integer> stack=new Stack<>();
        for (String s : tokens) {
            if (!isOperation(s)) {
                //压入数字字符
                stack.push(Integer.parseInt(s));
            }else {
                //运算符则弹出栈顶2个元素进行操作（先弹出的放运算符右边）
                int num2=stack.pop();
                int num1=stack.pop();
                switch (s){
                    case "+":
                        stack.push(num1+num2);
                        break;
                    case "-":
                        stack.push(num1-num2);
                        break;
                    case "*":
                        stack.push(num1*num2);
                        break;
                    case "/":
                        stack.push(num1/num2);
                        break;
                }
            }
        }
        return stack.pop();
    }

    private static boolean isOperation(String s) {
        if (s.equals("+") || s.equals("-") || s.equals("*") || s.equals("/")){
            //是运算符
            return true;
        }
        return false;
    }

    public boolean IsPopOrder (int[] pushV, int[] popV) {
        Stack<Integer> stack=new Stack<>();
        int j=0;
        for (int i = 0; i < pushV.length; i++) {
            stack.push(pushV[i]);
            while (!stack.empty() && j<popV.length && stack.peek()==popV[j]){
                stack.pop();
                j++;
            }
        }
        return stack.empty();
    }


    public static void main(String[] args) {

       /* System.out.print("无参r1生成10个[0,100)之间的随机整数:");
        Random r1 = new Random();
        for (int i = 0; i < 10; i++) {
            System.out.print(r1.nextInt(100)+" ");
        }
        System.out.println();

        System.out.print("无参r2生成10个[0,100)之间的随机整数:");
        Random r2 = new Random();
        for (int i = 0; i < 10; i++) {
            System.out.print(r2.nextInt(100)+" ");
        }
        System.out.println();


        System.out.print("种子数13的r3生成10个[0,100)之间的随机整数:");
        Random r3 = new Random(13); // 使用固定的种子数13
        for (int i = 0; i < 10; i++) {
            System.out.print(r3.nextInt(100)+" ");
        }
        System.out.println();

        System.out.print("种子数13的r4生成10个[0,100)之间的随机整数:");
        Random r4 = new Random(13); // 使用固定的种子数13
        for (int i = 0; i < 10; i++) {
            System.out.print(r4.nextInt(100)+" ");
        }*/

        //System.out.println(evalRPN(new String[]{"2","1","+","3","*"}));
//        Queue<Integer> q = new LinkedList<>();
//        // 从队尾入队列
//        q.offer(1);
//        q.offer(2);
//        q.offer(3);
//        q.offer(4);
//        q.offer(5);
//        System.out.println(q.size());//5
//        System.out.println(q.peek()); // 获取队头元素 1
//        q.poll();//弹出队头元素 1
//        System.out.println(q.poll()); // 从队头出队列，并将删除的元素返回 2
//        if(q.isEmpty()){
//            System.out.println("队列空");
//        }else{
//            System.out.println(q.size());//3
//        }

        LinkedList<Integer> stack=new LinkedList<>();
        stack.push(1);
        stack.push(2);
        stack.push(3);
        System.out.println(stack.peek());//1
    }
}

class MyQueue {
    Stack<Integer> inStack;
    Stack<Integer> outStack;

    public MyQueue() {
        inStack=new Stack<>();
        outStack=new Stack<>();
    }

    public void push(int x) {
        inStack.push(x);
    }

    public int pop() {
        if (empty()){
            return -1;//队列此时为空
        }
        if (outStack.empty()){
            while (!inStack.empty()){
                outStack.push(inStack.pop());
            }
        }
        return outStack.pop();
    }

    public int peek() {
        if (empty()){
            return -1;
        }
        if (outStack.empty()){
            while (!inStack.empty()){
                outStack.push(inStack.pop());
            }
        }
        return outStack.peek();
    }

    public boolean empty() {
        return inStack.empty() && outStack.empty();
    }
}


class MyStack {
    private Queue<Integer> qu1;
    private Queue<Integer> qu2;


    public MyStack() {
        qu1=new LinkedList<>();
        qu2=new LinkedList<>();
    }

    //入栈入到不为空的队列，都为空则入到qu1即可
    public void push(int x) {
        if (!qu1.isEmpty()){
            qu1.offer(x);
        }else if (!qu2.isEmpty()){
            qu2.offer(x);
        }else {
            qu1.offer(x);
        }
    }

    //出栈出不为空的队列size-1个。最后一个元素就是要出栈的元素
    public int pop() {
        if (empty()){
            return -1;//栈为空
        }
        if (!qu1.isEmpty()){
            int size=qu1.size();
            for (int i = 0; i < size - 1; i++) {
                qu2.offer(qu1.poll());
            }
            return qu1.poll();
        }else {
            int size=qu2.size();
            for (int i = 0; i < size - 1; i++) {
                qu1.offer(qu2.poll());
            }
            return qu2.poll();
        }
    }

    public int top() {
        if (empty()){
            return -1;//栈为空
        }
        if (!qu1.isEmpty()){
            int size=qu1.size();
            for (int i = 0; i < size - 1; i++) {
                qu2.offer(qu1.poll());
            }
            return qu1.peek();
        }else {
            int size=qu2.size();
            for (int i = 0; i < size - 1; i++) {
                qu1.offer(qu2.poll());
            }
            return qu2.peek();
        }
    }

    public boolean empty() {
        return qu2.isEmpty()&&qu1.isEmpty();
    }
}